#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "stack"
#include "TypeDefin.h"

using namespace std;

/*HJJ QQ479287006
 * 二叉树的前序遍历
 *给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * 输入：root = [1,null,2,3]
输出：[1,2,3]
 示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
 https://leetcode.cn/problems/binary-tree-preorder-traversal/
 * */


vector<int> preorderTraversal(TreeNode *root) {
    vector<int> ret;
    stack<TreeNode *> s;
    if (!root)
        return ret;
    s.push(root);

    while (!s.empty()) {

        TreeNode *temp = s.top();
        ret.push_back(temp->val);
        s.pop();

        //先顺着最左边走到底，然后逆着这个顺序不断回退，如果有右树，就进入右树。这个过程其实就是一个先进后出的过程，是符合stack栈的数据结构。所以代码如下
        //右边的树是最后才遍历到的，根据栈的性质应该第一个推进去，左边的是先遍历到，所以后面推进去。
        //这里为什么不用队列 那样就可以左右了》？ 那样直接遍历到右边子树了不符合了就
        if (temp->right) {
            s.push(temp->right);//先右边 后左边我擦妈妈妈妈的
        }
        if (temp->left) {
            s.push(temp->left);
        }

    }


    return ret;

}